#pragma once

enum Color {
	RED,
	BLACK
};

template <class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Color _color;

	RBTreeNode(const T& data) :
						_left(nullptr),
						_right(nullptr),
						_parent(nullptr),
						_color(RED),
						_data(data)
	                    {}
};

template <class K,class T,class keyofT>
class RBTree {
	typedef RBTreeNode<T> Node;
public:
		RBTree():
			_root(nullptr)
			{}


		void RotateL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;

			parent->_right = subRL;
			if (subRL)
				subRL->_parent = parent;

			Node* parentparent = parent->_parent;
			subR->_left = parent;
			parent->_parent = subR;

			if (parent == _root)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			else
			{
				if (parentparent->_left == parent)
				{
					parentparent->_left = subR;
					subR->_parent = parentparent;
				}
				if (parentparent->_right == parent)
				{
					parentparent->_right = subR;
					subR->_parent = parentparent;
				}
			}

		}

		void RotateR(Node* parent)
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;

			parent->_left = subLR;
			if (subLR)
				subLR->_parent = parent;

			Node* parentparent = parent->_parent;

			subL->_right = parent;
			parent->_parent = subL;
			if (parent == _root)
			{
				_root = subL;
				_root->_parent = nullptr;
			}
			else
			{
				if (parent == parentparent->_left)
					parentparent->_left = subL;
				if (parent == parentparent->_right)
					parentparent->_right = subL;

				subL->_parent = parentparent;
			}

		}

		bool Insert(const T& data)
		{
			if (_root == nullptr)
			{
				_root = new Node(data);
				_root->_color = BLACK;
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			keyofT kot;
			while (cur)
			{
				if (kot(cur->_data) < kot(data))
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (kot(cur->_data) > kot(data))
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(data);
			if (kot(parent->_data)< kot(data))
			{
				parent->_right = cur;
				cur->_parent = parent;
			}
			if (kot(parent->_data) > kot(data))
			{
				parent->_left = cur;
				cur->_parent = parent;
			}

			while (parent && parent->_color == RED)
			{
				Node* grandpa = parent->_parent;
				if (parent == grandpa->_left)
				{
					Node* uncle = grandpa->_right;
					if (uncle && uncle->_color == RED)
					{
						parent->_color = BLACK;
						uncle->_color = BLACK;
						grandpa->_color = RED;
						cur = grandpa;
						parent = cur->_parent;
					}
					else
					{
						if (cur == parent->_left)
						{
							RotateR(grandpa);
							parent->_color = BLACK;
							grandpa->_color = RED;
						}
						else
						{
							RotateL(parent);
							RotateR(grandpa);
							cur->_color = BLACK;
							grandpa->_color = RED;
						}
						break;
					}
				}
				else
				{
					Node* uncle = grandpa->_left;
					if (uncle && uncle->_color == RED)
					{
						parent->_color = BLACK;
						uncle->_color = BLACK;
						grandpa->_color = RED;
					
						cur = grandpa;
						parent = cur->_parent;
					}
					else
					{
						if (cur == parent->_right)
						{
							RotateL(grandpa);
							parent->_color = BLACK;
							grandpa->_color = RED;
						}
						else
						{
							RotateR(parent);
							RotateL(grandpa);
							cur->_color = BLACK;
							grandpa->_color = RED;
						}
						break;
					}
				}
			}
			_root->_color = BLACK;
		}
		void Inorder()
		{
			_Inorder(_root);
		}

		void _Inorder(Node* root)
		{
			if (root == nullptr)
				return;

			_Inorder(root->_left);
			cout << root->_kv.first << "-" << root->_kv.second << endl;
			_Inorder(root->_right);
		}

		bool isbalance()
		{
			if (_root&&_root->_color==RED)
				return false;
			int banchmark = 0;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_color == BLACK)
				{
					++banchmark;
					cur = cur->_left;
				}
			}
			int blacknum = 0;
			return _isbalance(_root, banchmark,blacknum);
		}

		bool _isbalance(Node*root,int banchmark,int blacknum)
		{
			if (root == nullptr)
			{
				if (banchmark != blacknum)
				{
					return false;
				}
				return true;
			}
			if (root->_color == RED && root->_parent->_color == RED)
				return false;
			if (root->_color == BLACK)
			{
				blacknum++;
			}
			return _isbalance(root->_left, banchmark, blacknum) && _isbalance(root->_right, banchmark, blacknum);
		}


private:
	Node* _root;

};

